package leetcode51_60;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author shhjiang_001
 * @create 2020-06-18 18:18
 */
public class Solution52 {
    int res = 0;
    public int totalNQueens(int n) {
        char[][] chars = new char[n][n];
        for (int i = 0;i < n;i++){
            for (int j = 0;j < n;j++){
                chars[i][j] = '.';
            }
        }
        int i= 0,j =0;
        int num = 0;
        method(chars,i,j,num);
        return res;
    }

    private void method(char[][] chars, int i, int j, int num) {
        if (num == chars.length){
            // 把符合的结果加到结果数组中
//            ArrayList<String> strings = new ArrayList<>();
//            for (int m = 0;m < chars.length;m++){
//                String s1 = new String(chars[m]);
////                String s = Arrays.toString(chars[m]);
//                strings.add(s1);
//            }
//            resList.add(strings);
            res++;
            return;
        }
        if (i == chars.length) return;
        boolean isFlag = true;
        int leRow = 0;
        int riRow = chars.length-1;
        int leLine = 0;
        int riLine = chars.length-1;
        // 判断行
        for (int m = leRow;m < riRow;m++){
            if (chars[m][j] == 'Q'){
                isFlag = false;
                break;
            }
        }
        // 判断列
        for (int m = leLine;m < riLine;m++){
            if (chars[i][m] == 'Q'){
                isFlag = false;
                break;
            }
        }

        int le = i;
        int ri = j;
        while (le < chars.length && le >=0 && ri >= 0 && ri < chars.length){
            if (chars[le][ri] == 'Q') {
                isFlag = false;
                break;
            }
            le++;
            ri++;
        }
        le = i;
        ri = j;
        while (le < chars.length && le >=0 && ri >= 0 && ri < chars.length){
            if (chars[le][ri] == 'Q') {
                isFlag = false;
                break;
            }
            le--;
            ri++;
        }
        le = i;
        ri = j;
        while (le < chars.length && le >=0 && ri >= 0 && ri < chars.length){
            if (chars[le][ri] == 'Q') {
                isFlag = false;
                break;
            }
            le++;
            ri--;
        }
        le = i;
        ri = j;
        while (le < chars.length && le >=0 && ri >= 0 && ri < chars.length){
            if (chars[le][ri] == 'Q') {
                isFlag = false;
                break;
            }
            le--;
            ri--;
        }
        if (isFlag){
            chars[i][j] = 'Q';
            num++;
            if (j==chars.length-1){
                method(chars,i+1,0,num);
                chars[i][j] = '.';
                num--;
                method(chars,i+1,0,num);
            }else {
                method(chars,i,j+1,num);
                chars[i][j] = '.';
                num--;
                method(chars,i,j+1,num);
            }
        }else {
            if (j==chars.length-1){
                method(chars,i+1,0,num);
            }else {
                method(chars,i,j+1,num);
            }
        }



    }
    @Test
    public void test() {
        Solution52 solution52 = new Solution52();
//        System.out.println(Arrays.asList(new int[]{1, 2, 3}).toString());
        int i = solution52.totalNQueens(4);
        System.out.println(i);
    }
}
